/* -*- c++ -*-
   SimpleList.h - A simple, doubly-linked list
   Copyright (C) 2011 Matthew Wahab <mwb.cde@gmail.com>

   This file is part of GCC-LLVMIR.

   GCC-LLVMIR is free software; you can redistribute it and/or modify it under
   the terms of the GNU General Public License as published by the Free
   Software Foundation; either version 3, or (at your option) any later
   version.

   GCC-LLVMIR is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or
   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   for more details.

   You should have received a copy of the GNU General Public License
   along with GCC-LLVMIR; see the file COPYING3.  If not see
   <http://www.gnu.org/licenses/>.  */

/* This is a C++ file. */

#ifndef SIMPLELIST_H
#define SIMPLELIST_H

namespace llvmir
{
  /*
   * SimpleList: Guarded list: SimpleList<Ty>: Double-linked list of nodes
   * of type Ty. Requires Ty to be descended from SimpleList::Node<Ty>,
   * or to have similar properties. Intended to be more light-weight
   * than std::list.
   *
   * SimpleList::Node: Node in a data list. Guarded to ensure that list
   * insertion/deletion operations are valid.  Uses of SimpleList can
   * inherit from SimpleList::Node to implement the required methods.
   */
  template <class Ty>
    class SimpleList
    {
      /*
       * List fields
       */
    protected:

      Ty* first_;    // First node in the list.
      Ty* last_;     // Last node in the list.

      /*
       * List nodes
       */
    public:
      class Node
      {
      protected:
	/* Fields */
	Ty* prev_node_;
	Ty* next_node_;

	// Containing list, used as a guard against invalid
	// insert/remove. Set to 0 iff node is not in a list.
	SimpleList<Ty>* list_;

      public:

	/* Accessors */
	void set_next(Ty* n)
	{
	  next_node_ = n;
	}
	Ty* next()
	{
	  return next_node_;
	}
	const Ty* next() const
	{
	  return next_node_;
	}

	void set_prev(Ty* n)
	{
	  prev_node_ = n;
	}
	Ty* prev()
	{
	  return prev_node_;
	}
	const Ty* prev() const
	{
	  return prev_node_;
	}

	void set_list(SimpleList<Ty>* n)
	{
	  list_ = n;
	}
	SimpleList<Ty>* list()
	  {
	    return list_;
	  }
	const SimpleList<Ty>* list() const
	{
	  return list_;
	}

	// Remove the element from its list.
	void remove()
	{
	  if (!this->list())
	    return;

	  if (this->list()->first_ == this)
	    this->list()->first_ = this->next();

	  if (this->list()->last_ == this)
	    this->list()->last_ = this->prev();

	  if (this->next())
	    (this->next())->set_prev(this->prev());

	  if (this->prev())
	    (this->prev())->set_next(this->next());

	  this->set_list(0);
	  this->set_prev(0);
	  this->set_next(0);
	}

	/* Constructor */
      Node(): prev_node_(0), next_node_(0), list_(0)
	  {}

	/* Destructor. */
	virtual ~Node()
	  {
	    this->remove();
	  }
      };

      /*
       * List 
       */

    public:
      /* Constructor */
    SimpleList() : first_(0), last_(0)
	{}

      // clear(): Clear the list, removing each item from the list.
      void clear()
      {
	Ty* next = last_;
	for (Ty* itr = first_;
	     itr != 0;
	     itr = next)
	  {
	    next = itr->next();
	    itr->set_next(0);
	    itr->set_prev(0);
	    itr->set_list(0);
	  }
	first_ = 0;
	last_ = 0;
      }

      /* Destructor */
      virtual ~SimpleList()
	{
	  this->clear();
	}

      /* Methods */

      // Test for an empty list.
      bool empty() const
      {
	return first_ == 0;
      }

      //  Get the first element in the list.
      Ty* front() const
      {
	return first_;
      }

      // Get the last element in the list.
      Ty* back() const
      {
	return last_;
      }

      // Test whether elem is a member of the list.
      bool member(const Ty* elem) const
      {
	if (elem == 0)
	  return false;

	if (elem->list() == this)
	  return true;

	return false;
      }

      // Insert elem at the start of the list. Fail if elem is already
      // in a list.
      void push_front(Ty* elem)
      {
	if (elem == 0)
	  return;

	assert(elem->list() == 0
	       && "ELement is already in a list");

	// Handle an empty list
	if (first_ == 0)
	  {
	    assert(last_ == 0);
	    first_ = elem;
	    last_ = elem;
	    elem->set_next(0);
	    elem->set_prev(0);
	  }
	else // Insert into a non-empty list
	  {
	    first_->set_prev(elem);
	    elem->set_next(first_);
	    elem->set_prev(0);

	    first_ = elem;
	  }

	// Set the list
	elem->set_list(this);
      }

      // Insert elem at the end of the list. Fail if elem is already
      // in a list.
      void push_back(Ty* elem)
      {
	if (elem == 0)
	  return;

	assert(elem->list() == 0
	       && "ELement is already in a list");

	// Handle an empty list
	if (first_ == 0)
	  {
	    assert(last_ == 0);
	    first_ = elem;
	    last_ = elem;
	    elem->set_next(0);
	    elem->set_prev(0);
	  }
	else // Insert into a non-empty list
	  {
	    last_->set_next(elem);
	    elem->set_prev(last_);
	    elem->set_next(0);
	    last_ = elem;
	  }

	// Set the list
	elem->set_list(this);
      }

      // Remove elem from the list. Fail if elem is not in the list.
      void remove(Ty* elem)
      {
	assert(elem != 0);
	Ty* elem_next = elem->next();
	Ty* elem_prev = elem->prev();

	if (elem->list() != this)
	  return;

	assert(elem->list() == this
	       && "Can't remove an element from a list it isn't in.");

	assert(((elem_next == 0) && (elem_prev == 0))
	       || (elem_next != elem_prev));

	elem->set_next(0);
	elem->set_prev(0);

	if (first_ == elem)
	  first_ = elem_next;
	if (last_ == elem)
	  last_ = elem_prev;

	if (elem_next != 0)
	  elem_next->set_prev(elem_prev);
	if (elem_prev != 0)
	  elem_prev->set_next(elem_next);

	// Set the list
	elem->set_list(0);
      }

      // Length of the list.
      unsigned length() const
      {
	unsigned len = 0;
	for (Ty* elem = this->front();
	     elem != 0;
	     elem = elem->next())
	  {
	    len += 1;
	  }
	return len;
      }

      // append(l): Move the contents out of l, adding them to the end
      // of this list.
      SimpleList<Ty>* append(SimpleList<Ty>* other)
      {
	Ty* next_elem = 0;

	if (!other)
	  return this;

	for (Ty* elem = other->front();
	     elem != 0;
	     elem = next_elem)
	  {
	    next_elem = elem->next();
	    
	    // Remove elem from the other list.
	    other->remove(elem);
	    // Add it to this list.
	    this->push_back(elem);
	  }
	return this;
      }

      // clear_content(): Clear the list, deleting each item in the list.
      void clear_content()
      {
	Ty* next_elem = last_;
	for (Ty* itr = first_;
	     itr != 0;
	     itr = next_elem)
	  {
	    next_elem = itr->next();
	    delete itr;
	  }
	first_ = 0;
	last_ = 0;
      }

      // Replace an elem in the list. Fail if elem is not in the list.
      void replace(Ty* elem, Ty* other)
      {
	if (!elem || !other
	    || elem->list() != this
	    || other->list() != 0)
	  return;

	  other->set_list(elem->list());

	  other->set_next(elem->prev());
	  if (elem->prev() != 0)
	    (elem->prev())->set_next(other);

	  other->set_prev(elem->next());
	  if (elem->next() != 0)
	    (elem->next())->set_prev(other);
	    
	  elem->set_list(0);
	  elem->set_prev(0);
	  elem->set_next(0);

	  // Update the list.
	  if (first_ == elem)
	    first_ = other;

	  if (last_ == elem)
	    last_ = other;
      }
    };
} // namespace llvm


/* End of file. */
#endif /* SIMPLELIST_H */
